#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>


#define MAP_X 15
#define MAP_Y 15
/*
 *
 *  S-> SR 0.20
 *      SL 0.20
 *      SS 0.50
 *      s  0.10
 *
 *  R-> RS 0.7
 *      Rs 0.3
 *
 *  L-> LS 0.7
 *      Ls 0.3
 *
 *  s-> sS 0.40
 *      sR 0.10
 *      sL 0.10
 *      ss 0.30
 * */


using namespace std;
typedef struct Proposition{

    string leftSide;
    string rightSide;
    double probability;
    double random;

} Proposition;



enum direction {U=0, L=1, D=2, R=3};

typedef struct Turtle{

    int x;
    int y;
    int dir;

} Turtle;


string getPattern(string init);
Proposition getNextProposition(string leftSide);
void moveTurtle(string moves);
void moveStraight(bool draw);
void drawMap();
int mod(int x, int m);

int map[MAP_Y][MAP_X];
Turtle t = {MAP_Y/2,MAP_X/2, U};

const int iterations = 4;
string init = "S";
vector<Proposition> propositions;

int main(int argc, char **argv)
{

    srand(time(NULL));

    Proposition S1 = {"S", "SR", 0.20, 0.0};
    Proposition S2 = {"S", "SL", 0.20, 0.0};
    Proposition S3 = {"S", "SS", 0.50, 0.0};
    Proposition S4 = {"S", "Ss", 0.10, 0.0};

    Proposition R1 = {"R", "RS", 0.70, 0.0};
    Proposition R2 = {"R", "Rs", 0.30, 0.0};

    Proposition L1 = {"L", "LS", 0.70, 0.0};
    Proposition L2 = {"L", "Ls", 0.30, 0.0};

    Proposition s1 = {"s", "sR", 0.40, 0.0};
    Proposition s2 = {"s", "sL", 0.10, 0.0};
    Proposition s3 = {"s", "sS", 0.10, 0.0};
    Proposition s4 = {"s", "ss", 0.30, 0.0};

    propositions.push_back(S1);
    propositions.push_back(S2);
    propositions.push_back(S3);
    propositions.push_back(S4);
    propositions.push_back(R1);
    propositions.push_back(R2);
    propositions.push_back(L1);
    propositions.push_back(L2);
    propositions.push_back(s1);
    propositions.push_back(s2);
    propositions.push_back(s3);
    propositions.push_back(s4);


    string result = init;
    int i;
    for (i = 0; i < iterations; ++i) {
        result = result + getPattern(result);
    }


    moveTurtle(result);
    drawMap();
    return 0;
}

int mod(int x, int m) {
    return (x%m + m)%m;
}


void moveTurtle(string moves){


    for (int i = 0; i < moves.size(); ++i) {

        switch (moves.at(i)) {
        case 'S':
            moveStraight(true);
            break;

        case 'L':
            t.dir = mod((t.dir+1), 4);
            break;

        case 'R':
            t.dir = mod((t.dir-1), 4);
            break;

        default:
            moveStraight(false);
            break;
        }


    }

}


void drawMap(){

       for (int i = 0; i < MAP_Y; ++i) {
           for (int j = 0; j < MAP_X; ++j) {
if(map[j][i] == 1)
            cout << "\033[0;31m" << map[j][i] << " \033[0m";
else
		cout << map[j][i] << " ";
        }

        cout << endl;
    }

       cout << "--------------------------------------" << endl;

}

void moveStraight(bool draw){


    switch (t.dir) {
    case U:
        t.y = t.y -1;
        break;
    case D:
        t.y = t.y + 1;
        break;
    case L:
        t.x = t.x - 1;
        break;
    case R:
        t.x = t.x + 1;
        break;
    default:

        cout << "Problem with direction " << t.dir << endl;
        exit(0);
        break;
    }



    if(t.x == MAP_Y || t.x < 0){
        return;
        t.x = MAP_Y/2;
    }

    if(t.y == MAP_X || t.y < 0){
        return;
        t.y = MAP_X/2;
    }


    if(draw){
        map[t.x][t.y] = 1;
    }

}

string getPattern(string init){

    string result = "";

    for (int j = 0; j < init.size(); ++j) {
        result = result + getNextProposition(init.substr(j,1)).rightSide;
    }

    return result;
}


Proposition getNextProposition(string leftSide){

    vector<Proposition> p;

    for (int var = 0; var < propositions.size(); ++var) {
        if(propositions[var].leftSide == leftSide){

            propositions[var].random =  (rand() % 1000) / 1000.0 - (1-propositions[var].probability);
            p.push_back(propositions[var]);

        }
    }

    double max_p = -10;
    int index = 0;
    for (int var = 0; var < p.size(); ++var) {

        if(p[var].random > max_p){
            max_p = p[var].random;
            index = var;
        }

    }

    return p[index];

}
